#include <iostream>


int N3(const int A[], int N) {
    int ThisSum, MaxSum, i, j, k;
    MaxSum = 0;
    for(i=0;i<N;i++) //i->[0,n-1]
        for (j = i; j < N; j++) {  //j->[i,n-1]
            ThisSum = 0;
            for (k = i; k <= j; k++) //k->[i,j]
                ThisSum += A[k];
            if (ThisSum > MaxSum)
                MaxSum = ThisSum;
        }
    return MaxSum;
}

void N2(const int A[], int N) {
    int ThisSum, MaxSum, i, j;
    MaxSum = 0;
    for (i = 0; i < N; i++) { //i->[0,n-1]
        ThisSum = 0;
        for (int j = i; j < N; j++) { //j->[i,n-1]
            ThisSum += A[j];
            if (ThisSum > MaxSum)
                MaxSum = ThisSum;
        }
    }
    std::cout << "max=" << MaxSum << "\n";
}

int Max3(int a, int b, int c) {
    if (a >= b&& a >= c)
        return a;
    if (b >= a&& b >= c)
        return b;
    if (c >= b&& c >= a)
        return c;
}

int NLogN(const int A[], int Left, int Right) {
    int MaxLeftSum, MaxRightSum;
    int MaxLeftBorderSum, MaxRightBorderSum;
    int LeftBorderSum, RightBorderSum;
    int Center, i;
    if (Left == Right)
        if (A[Left] > 0)
            return A[Left];
        else
            return 0;
    Center = (Left + Right) / 2;
    MaxLeftSum = NLogN(A, Left, Center);
    MaxRightSum = NLogN(A, Center + 1, Right);
    MaxLeftBorderSum = 0; LeftBorderSum = 0;
    for (i = Center; i >= Left; i--) {
        LeftBorderSum += A[i];
        if (LeftBorderSum > MaxLeftBorderSum)
            MaxLeftBorderSum = LeftBorderSum;
    }
    MaxRightBorderSum = 0; RightBorderSum = 0;
    for (i = Center + 1; i <= Right; i++) {
        RightBorderSum += A[i];
        if (RightBorderSum > MaxRightBorderSum)
            MaxRightBorderSum = RightBorderSum;
    }
    return Max3(MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum);
}

void NLogNWrapper(const int A[], int N) {
    std::cout << "max=" << NLogN(A, 0, N - 1) << "\n";
}

int main()
{
	const int N = 6;
	int a[N] = { -2,11,-4,13,-5,-2 };
    //N2(a, N);
    NLogNWrapper(a, N);
}
